package com.xigua._高级数据结构或系统;

/**
 * @author LiRongHua
 * @version 1.0.0
 * @ClassName _307_区域和检索_数组可修改.java
 * @Description 给你一个数组 nums ，请你完成两类查询。

其中一类查询要求 更新 数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right
实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值 更新 为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-mutable
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @createTime 2022年04月04日 12:19:00
 */
public class _307_区域和检索_数组可修改 {

    public static void main(String[] args) {
        NumArray numArray = new NumArray(new int[]{1,3,5});
        System.out.println(numArray.sumRange(0,2));
        numArray.update(1,2);
        System.out.println(numArray.sumRange(0,2));
    }

}

class NumArray {

    private int[] nums;
    private int[] sums;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.sums = new int[nums.length+1];
        this.sums[0] = 0;
        this.sums[1] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i+1] = sums[i]+nums[i];
        }
    }

    public void update(int index, int val) {
        int num = nums[index];
        int diff = val - num;
        for (int i = index+1; i < sums.length; i++) {
            sums[i] = sums[i] +diff;
        }
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        return sums[right+1] - sums[left];
    }
}

